Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 12324 - Philip J. Fry Problem / zubieta.cpp
blob281933490ec35bf34c498aa66bb673f444dfcfe1
1 #include <iostream>
2 #include <cmath>
3 #include <vector>
4 #include <map>
5 #include <stack>
6 #include <queue>
7 #include <deque>
8 #include <sstream>
9 #include <list>
10 #include <set>
11 #include <algorithm>
12 #include <stdio.h>
13 #include <stdlib.h>
15 using namespace std;
17 int n;
18 int viajes[105];
19 int bolas[105];
20 int mat[105][105*105];
22 int func(int a, int b, bool c){
23 if(mat[a][b])
24 return mat[a][b];
26 int thisTravel = viajes[a]/(c?2:1);
27 b += bolas[a];
28 if(a!=n-1)
29 if(b)
30 mat[a][b] = (thisTravel += min(func(a+1,b-1,1),func(a+1,b,0)));
31 else
32 mat[a][b] = (thisTravel += func(a+1,b,0));
34 return thisTravel;
37 int main(){
38 scanf("%d",&n);
39 while(true){
40 if(!n){
41 break;
43 for(int z=0;z<n;++z){
44 scanf("%d",&viajes[z]);
45 scanf("%d",&bolas[z]);
47 for(int z=0;z<n;++z)
48 for(int y=0;y<n*n;++y)
49 mat[z][y]=0;
50 printf("%d\n",func(0,0,0));
51 scanf("%d",&n);